"""This module supports word validation."""

__author__ = "Solon Gordon (solongordon@gmail.com)"

import unittest

class WordList:
  """A class that acts as the "dictionary" for a Scrabble game.
  
  If the words parameter is a string, it is expected to be a filename.  If it is
  any other type of iterable object it is assumed to contain straings to be
  inserted.  It defaults to the TWL 2006 word list file.
  """
  def __init__(self, words="TWL06.txt"):
    # If the input type was a string, open the file.  Otherwise we can just read
    # from it directly.
    if (type(words) == str):
      words = open(words)

    # Build word tries in both forward and reverse directions.
    # Use the pound sign as a word-end character (or in the reverse trie, as a
    # word-beginning character).
    self.trie = Trie()
    self.reverse_trie = Trie()
    for word in words:
      # Prepare our word for insertion.  Remove any non-alphabetical characters.
      word = "".join([c for c in word.strip().upper() if c.isalpha()])

      # Add our word.
      self.trie.AddWord(word + '#')
      self.reverse_trie.AddWord(word[::-1] + '#')
  
  def IsValidWord(self, word):
    """Tests if a word is in the word list."""
    word = word.upper()
    return '#' in self.trie.LookUp(word).keys()

  def NextLetterOptions(self, prefix):
    """Returns a list of letters that could follow the prefix to build towards
    a valid word.
    
    For instance, NextLetterOptions('GHOS') returns ['T'].
    """
    prefix = prefix.upper()
    letters = sorted(self.trie.LookUp(prefix).keys())

    # Filter out anything that is not an uppercase letter.
    return filter(lambda x: 64 < ord(x) < 91, letters)
    
  def PreviousLetterOptions(self, suffix):
    """Returns a list of letters that could precede the suffix to build
    backwards towards a valid word.
    
    For instance, PreviousLetterOptions('CRABBLE') returns ['S'].
    """
    # Reverse the suffix so it can be used as a prefix in the trie lookup.
    prefix = suffix.upper()[::-1]
    letters = sorted(self.reverse_trie.LookUp(prefix).keys())

    # Filter out anything that is not an uppercase letter.
    return filter(lambda x: 64 < ord(x) < 91, letters)

class Trie:
  """A simple word trie class.
  
  The trie is stored as nested dictionaries, where the keys of the dictionary
  represent the nodes of the tree.
  """
  def __init__(self):
    self.trie = {}

  def AddWord(self, word):
    """Adds a string to the trie."""
    trieref = self.trie
    for letter in word:
      if letter not in trieref.keys():
        trieref[letter] = {}
      trieref = trieref[letter]

  def LookUp(self, word):
    """Returns the child trie of the word.""" 
    if len(word) == 0:
      return self.trie
    try:
      if len(word) == 1:
        return self.trie[word]
      return self.LookUp(word[:-1])[word[-1]]
    except KeyError:
      return {}

class WordListTest(unittest.TestCase):
  def setUp(self):
    # Create a word list with 4 words.
    self.list = WordList(["gabe", "solon", "armadillo", "armad"])

  def testWordThatDoesntExist(self):
    self.assert_(False == self.list.IsValidWord("NOTAWORD"))

  def testWordThatDoesExist(self):
    self.assert_(True == self.list.IsValidWord("ARMADILLO"))

  def testWordThatWasUppercased(self):
    self.assert_(True == self.list.IsValidWord("gabe")) 

  def testWordThatsASubstringOfAnother(self):
    self.assert_(True == self.list.IsValidWord("ARMAD")) 

  def testAllSubstringsArentWords(self):
    self.assert_(False == self.list.IsValidWord("SOLO"))

  def testOctothorpGetIgnored(self):
    self.list = WordList(["ga#be"])
    self.assert_(True == self.list.IsValidWord("GABE")) 
    self.assert_(False == self.list.IsValidWord("GA")) 

class InfiniteWordList(WordList):
  """A WordList containing all combinations of characters.  Used for testing."""
  def __init__(self):
    WordList.__init__(self, [ ])

  def IsValidWord(self, word):
    return True

  def NextLetterOptions(self, prefix):
    return [x for x in "ABCDEFGHIJKLMNOPQRSTUVWXYZ"]

  def PreviousLetterOptions(self, suffix):
    return NextLetterOptions(suffix)

class InfiniteWordListTest(unittest.TestCase):
  def testHasWord(self):
    wordlist = InfiniteWordList()
    self.assert_(True == wordlist.IsValidWord("TOTALLYNOTVALID"))

if __name__ == "__main__":
  unittest.main()
